package cn.aylog.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 基数排序
 */
public class RadixSort {
    public static void main(String[] args) {
        // int arr[] = {8,9,1,7,20,2,5,4,6};
        int len = 80000;
        int[] arr = new int[len];
        for(int i=0; i<len; i++) {
            arr[i] = (int)(Math.random()*8000000);
        }
        long start = System.currentTimeMillis();
        radixSort(arr); // 30+ 20+ 1451 500+
        long end = System.currentTimeMillis();
        System.out.println("排序耗时: " + (end - start));
        // System.out.println(Arrays.toString(arr));
    }

    /**
     * 比原来(radixSort2)慢3倍
     * @param arr
     */
    public static void radixSort(int[] arr) {
        int len = arr.length;
        // 定义桶
        List<Integer>[] buckets = new List[10];
        for (int i=0; i<buckets.length; i++) buckets[i] = new ArrayList<>();
        // 定义每个桶的有效长度指针,一一对应
        int radix, pos = 10;
        while(true) {
            for (int x = 0; x < len; x++) {
                radix = arr[x] % pos / (pos/10);
                // 将数据存入桶中,并将该桶的有效数据长度增加
                buckets[radix].add(arr[x]);
            }
            if(buckets[0].size() == len) break; // 当所有的元素都在0的数组时表示排序结束
            int index = 0;
            // 将每个桶中的数据,按照有效个数重新取回到原数组
            for (List<Integer> list : buckets) {
                for (int li : list) {
                    arr[index++] = li;
                }
                list.clear();
            }

            // 基数位置往后前移, 个,十,百,千...
            pos *= 10;
        }
    }

    public static void radixSort2(int[] arr) {
        int len = arr.length;
        // 定义桶
        int[][] buckets = new int[10][len];
        // 定义每个桶的有效长度指针,一一对应
        int[] points = new int[10];
        int radix, pos = 10;
        while(true) {
            for (int x = 0; x < len; x++) {
                radix = arr[x] % pos / (pos/10);
                // 将数据存入桶中,并将该桶的有效数据长度增加
                buckets[radix][points[radix]++] = arr[x];
            }
            if(points[0] == len) break; // 当所有的元素都在0的数组时表示排序结束
            int index = 0;
            int pLen = points.length;
            // 将每个桶中的数据,按照有效个数重新取回到原数组
            for (int x = 0; x < pLen; x++) {
                int size = points[x];
                for (int y = 0; y < size; y++) {
                    arr[index++] = buckets[x][y];
                }
                // 数据长度重置
                points[x] = 0;
            }
            // 基数位置往后前移, 个,十,百,千...
            pos *= 10;
        }
    }
}
